#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 路径总和 -- 递归
// 路径总和II  --- dfs
// 路径之和III  ----dfs  栈溢出
// 将有序数组转化为二叉搜索树
// 二叉树的中序遍历 -- 非递归
// 二叉树的最大高度
// 翻转二叉树
// 二叉树的直径
// 二叉树的右视图
// 二叉树的最近公共祖先

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 路径总和 -- 递归
class Solution
{
public:
    bool hasPathSum(TreeNode *root, int targetSum)
    {
        if (root == nullptr)
            return false;
        if (root->left == nullptr && root->right == nullptr && root->val == targetSum)
            return true;

        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

// 路径总和II  --- dfs
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    int sum = 0, target;
    vector<vector<int>> pathSum(TreeNode *root, int targetSum)
    {
        target = targetSum;
        dfs(root);
        return ans;
    }

    void dfs(TreeNode *root)
    {
        if (root == nullptr)
            return;
        sum += root->val;
        path.push_back(root->val);
        if (root->left == nullptr && root->right == nullptr && sum == target)
        {
            ans.push_back(path);
        }
        dfs(root->left);
        dfs(root->right);

        // 恢复路径和路径和
        sum -= root->val;
        path.pop_back();
    }
};

// 路径之和III  ----dfs  栈溢出
class Solution
{
public:
    int rootSum(TreeNode *root, int target)
    {
        if (root == nullptr)
            return 0;
        int ret = 0;

        if (root->val == target)
        {
            ret++;
        }

        ret += rootSum(root->left, target - root->val);
        ret += rootSum(root->right, target - root->val);

        return ret;
    }
    int pathSum(TreeNode *root, int targetSum)
    {
        if (root == nullptr)
            return 0;

        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);

        return ret;
    }
};

// 路径之和III  ----dfs  前缀和
class Solution
{
public:
    unordered_map<long long, int> prefix;
    int target = 0;
    int dfs(TreeNode *root, long long cur)
    {
        if (root == nullptr)
            return 0;

        int ret = 0;
        cur += root->val;
        if (prefix.count(cur - target))
        {
            ret = prefix[cur - target];
        }

        prefix[cur]++;
        ret += dfs(root->left, cur);
        ret += dfs(root->right, cur);

        prefix[cur]--;

        return ret;
    }
    int pathSum(TreeNode *root, int targetSum)
    {
        prefix[0] = 1;
        target = targetSum;
        return dfs(root, 0);
    }
};

// 将有序数组转化为二叉搜索树
class Solution
{
public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {
        return dfs(nums, 0, nums.size() - 1);
    }

    TreeNode *dfs(vector<int> &nums, int left, int right)
    {
        if (left > right)
            return nullptr;

        // 以中间节点作为根节点
        int mid = (left + right) / 2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);

        return root;
    }
};

// 二叉树的中序遍历 -- 非递归
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> ans;
        stack<TreeNode *> st;
        TreeNode *cur = root;
        while (cur || st.size())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode *top = st.top();
            ans.push_back(top->val);
            st.pop();

            cur = top->right;
        }

        return ans;
    }
};

// 二叉树的最大高度
class Solution
{
public:
    int ans;
    int maxDepth(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

class Solution
{
public:
    int maxDepth(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        queue<TreeNode *> q;
        q.push(root);
        int ans = 0;
        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                TreeNode *node = q.front();
                q.pop();
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            ans++;
        }

        return ans;
    }
};

// 翻转二叉树
class Solution
{
public:
    TreeNode *invertTree(TreeNode *root)
    {
        if (root == nullptr)
            return nullptr;

        TreeNode *left = invertTree(root->left);
        TreeNode *right = invertTree(root->right);

        root->left = right;
        root->right = left;

        return root;
    }
};

class Solution
{
public:
    TreeNode *invertTree(TreeNode *root)
    {
        if (root == nullptr)
            return nullptr;
        queue<TreeNode *> q;
        q.push(root);

        while (q.size())
        {
            TreeNode *node = q.front();
            q.pop();

            TreeNode *tmp = node->left;
            node->left = node->right;
            node->right = tmp;

            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }

        return root;
    }
};

// 对称二叉树
class Solution
{
public:
    bool isSametree(TreeNode *root1, TreeNode *root2)
    {
        if (root1 == nullptr && root2 == nullptr)
            return true;
        if (root1 == nullptr || root2 == nullptr)
            return false;
        if (root1->val != root2->val)
            return false;
        return isSametree(root1->left, root2->right) && isSametree(root1->right, root2->left);
    }
    bool isSymmetric(TreeNode *root)
    {
        if (root == nullptr)
            return true;
        return isSametree(root->left, root->right);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        if (root == nullptr)
            return true;
        return bfs(root, root);
    }

    bool bfs(TreeNode *root1, TreeNode *root2)
    {
        queue<TreeNode *> q;
        q.push(root1);
        q.push(root2);

        while (q.size())
        {
            TreeNode *node1 = q.front();
            q.pop();
            TreeNode *node2 = q.front();
            q.pop();

            if (node1 == nullptr && node2 == nullptr)
                continue;
            if (node1 == nullptr || node2 == nullptr)
                return false;

            if (node1->val != node2->val)
                return false;

            q.push(node1->left);
            q.push(node2->right);

            q.push(node1->right);
            q.push(node2->left);
        }

        return true;
    }
};

// 二叉树的直径
class Solution
{
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode *root)
    {
        dfs(root);
        return ans - 1;
    }

    // 计算树的深度,ans更新节点数
    int dfs(TreeNode *root)
    {
        if (root == nullptr)
            return 0;

        int left = dfs(root->left);
        int right = dfs(root->right);

        ans = max(ans, left + right + 1);
        return max(left, right) + 1;
    }
};

// 二叉树的右视图
class Solution
{
public:
    vector<int> rightSideView(TreeNode *root)
    {
        if (root == nullptr)
            return {};
        vector<int> ans;
        queue<TreeNode *> q;
        q.push(root);
        while (q.size())
        {
            int size = q.size();
            while (size--)
            {
                TreeNode *node = q.front();
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
                if (size == 0)
                {
                    ans.push_back(q.front()->val);
                }
                q.pop();
            }
        }

        return ans;
    }
};

class Solution
{
public:
    unordered_map<long long, int> prefix;
    int target = 0;
    int dfs(TreeNode *root, long long cur)
    {
        if (root == nullptr)
            return 0;

        int ret = 0;
        cur += root->val;
        if (prefix.count(cur - target))
        {
            ret = prefix[cur - target];
        }

        prefix[cur]++;
        ret += dfs(root->left, cur);
        ret += dfs(root->right, cur);

        prefix[cur]--;

        return ret;
    }
    int pathSum(TreeNode *root, int targetSum)
    {
        prefix[0] = 1;
        target = targetSum;
        return dfs(root, 0);
    }
};

// 二叉树的最近公共祖先
class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (root == nullptr)
            return nullptr;

        if (root == p || root == q)
            return root;

        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right)
            return root;
        if (left)
            return left;
        else
            return right;
    }
};